<!DOCTYPE html>
<html lang="en">
<head>
  <title>数独求解</title>
  <meta charset="UTF-8">
  <meta name="description" content="ltoddy's blog">
  <meta name="author" content="liutao">
  <meta name="author" content="ltoddy">
  <meta name="author" content="just for fun">

  <link rel="icon" href="../../static/me.jpg">
  <!-- 最新版本的 Bootstrap 核心 CSS 文件 -->
  <link rel="stylesheet" href="https://cdn.bootcss.com/bootstrap/3.3.7/css/bootstrap.min.css"
        integrity="sha384-BVYiiSIFeK1dGmJRAkycuHAHRg32OmUcww7on3RYdg4Va+PmSTsz/K68vbdEjh4u" crossorigin="anonymous">

  <!-- jQuert Microsoft CDN -->
  <script src="https://ajax.aspnetcdn.com/ajax/jQuery/jquery-3.3.1.min.js"></script>
  <!-- 最新的 Bootstrap 核心 JavaScript 文件 -->
  <script src="https://cdn.bootcss.com/bootstrap/3.3.7/js/bootstrap.min.js"
          integrity="sha384-Tc5IQib027qvyjSMfHjOMaLkfuWVxZxUPnCJA7l2mCWNIpG9mGCD8wGNIcPD7Txa"
          crossorigin="anonymous"></script>
</head>
<body>
<div class="container">
  <div class="page-header">
    <h3>数独</h3>
  </div>
  <p><strong>题目描述</strong></p>
  <p>一个9×9的矩阵由9个3*3的子矩阵组成，其中每个3*3矩阵都由1-9这9个数字组成，且数独矩阵中每行、每列都没有重复数字。
    现有一个残缺不全的数独矩阵，编程完成它。（测试用例都只有1个解）</p>
  <p><strong>输入</strong></p>
  <p>输入数据为一个9行9列的矩阵，0表示残缺的数</p>
  <p><strong>输出</strong></p>
  <p>输入数据为一个9行9列的矩阵，每行的两个数之间有一个空格。（注意审题，即每行的末尾是没有空格的）</p>
  <p><strong>样例输入</strong></p>
  <pre><code>5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9 </code></pre>
  <p><strong>样例输出</strong></p>
  <pre><code>5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9</code></pre>

  <hr>

  <pre><code>#include &lt;stdio.h&gt;

int sudoku[9][9] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
};
int flag = 0;

int check_position(int x, int y, int u)
{
    for (int i = 0; i < 9; i++) {
        if (sudoku[x][i] == u || sudoku[i][y] == u) {
            return 0;
        }
    }
    int row = x / 3 * 3, col = y / 3 * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (sudoku[row + i][col + j] == u) {
                return 0;
            }
        }
    }
    return 1;
}

void printer()
{
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d%c", sudoku[i][j], j == 8 ? '\n' : ' ');
        }
    }
}

void dfs(int x, int y)
{
    if (flag) return;
    if (x == 9 && y == 0) {
        flag = 1;
        printer();
    }
    if (y == 9) {
        dfs(x + 1, 0);
    }

    if (sudoku[x][y]) {
        dfs(x, y + 1);
    } else {
        for (int i = 1; i <= 9; i++) {
            if (check_position(x, y, i)) {
                sudoku[x][y] = i;
                dfs(x, y + 1);
                sudoku[x][y] = 0;
            }
        }
    }
}

int main()
{
    dfs(0, 0);
    return 0;
} </code></pre>
  <a href="https://github.com/ltoddy/ltoddy.github.io" target="_blank"><img
      style="position: absolute; top: 0; right: 0; border: 0;"
      src="https://camo.githubusercontent.com/38ef81f8aca64bb9a64448d0d70f1308ef5341ab/68747470733a2f2f73332e616d617a6f6e6177732e636f6d2f6769746875622f726962626f6e732f666f726b6d655f72696768745f6461726b626c75655f3132313632312e706e67"
      alt="Fork me on GitHub"
      data-canonical-src="https://s3.amazonaws.com/github/ribbons/forkme_right_darkblue_121621.png">
  </a>
</div>
</body>
</html>